第64题(第3空)已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵A
1A
2......A
n相乘的计算顺序具有最优子结构,即A
1A
2......A
n的最优计算顺序包含其子问题A
1A
2......A
k和A
k+1A
k+2……A
n(1≤k
可以列出其递归式为:
其中,Ai的维度为pi-1*pi,m[i,j]表示AiAi+1……Aj最优计算顺序的相乘次数。
先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策略为( )。算法的时间复杂度为( ),空间复杂度为( )。
给定一个实例,(p0p1……p5)=(20,15,4,10,20,25),最优计算顺序为( )。